# -*- coding: utf-8 -*-

''' Autor: Neuza Figueira - n.º 6036 '''

from random import uniform
from time import clock
import matplotlib.pyplot as plt

class SelectionSort():
        ''' Class to handle Selection sort implementation and testing.'''

        def selection_sort(self, A):
                '''Python Implementation of Selection sort.'''
                '''@param A -> List to sort.'''
                for i in range(0, len(A)-1):
                        minimum = 1
                        for j in range(i + 1, len(A)):
                                if A[j] < A[i]:
                                        minimum = j
                                        t = A[i]
                                        A[i] = A[minimum]
                                        A[minimum] = t

                return A


        def testSelectionSort(self):
                    '''Testing the complexity of Selection sort.'''
                    Z = range(50, 1050, 50)
                    T = []
                    M = 50
                    for n in Z:
                        A = [ uniform(0.0, 1.0) for k in xrange(n)]
                        tempos = []
                        for k in range(M):
                            t1 = clock()
                            self.selection_sort(A)
                            t2 = clock()
                            tempos.append(t2-t1)
                        media = reduce(lambda x, y: x + y, tempos) / len(tempos)
                        var = reduce(lambda x, y: x + (y-media)**2, [0] + tempos) / len(tempos)
                        
                        T.append((n,media, var))

                    X = [n for n, media, var in T]
                    Y = [media for n, media, var in T]
                    ct = 13e6
                    Z = [n**2 / ct for n, media, var in T]


                    plt.grid(True)
                    plt.ylabel(u'T(n) - tempo de execução médio em segundos')
                    plt.xlabel(u'n - número de elementos')
                    plt.plot(X,Y,'rs', label="resultado experimental")
                    plt.plot(X, Z, 'b^', label=u"previsão teórica")
                    plt.legend()
                    plt.show()
                    pass
